#include <iostream>
#include <string>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if( !head )
            return NULL;

        int len = 0;
        ListNode *p = head;
        while( p ){
            len++;
            p = p->next;
        }

        if( n > len )
            return NULL;
        if( n == len ){
            p = head->next;
            delete head;
            return p;
        }
        
        int step = len - n;
        p = head;
        ListNode *first = head->next;
        ListNode *second = head;
        while( --step ){
            first = first->next;
            second = second->next;
        }
        second->next = first->next;
        delete first;
        return head;
    }
};


class Solution
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        ListNode** t1 = &head, *t2 = head;
        while( --n )
        {
            t2 = t2->next;
        }
        while( t2->next )
        {
            t1 = &((*t1)->next);
            t2 = t2->next;
        }
        *t1 = (*t1)->next;
        return head;
    }
};
